Proving termination of associative commutative rewriting systems by rewriting
Identifieur interne : 00E716 ( Main/Exploration ); précédent : 00E715; suivant : 00E717Proving termination of associative commutative rewriting systems by rewriting
Auteurs : I. Gnaedig ; Pierre Lescanne [France]Source :
English descriptors
- KwdEn :
Abstract
We propose in this paper a special reduction ordering for proving termination of Associative Commutative (AC in short) rewriting systems. This ordering is based on a transformation of the terms by a rewriting system with rules similar to distributivity. We show this is a reduction ordering which works in the AC case since it is AC-commuting, and which provides an automatizable termination tool, since it is stable by instanciation. Thereafter, we show cases where this ordering fails, and propose an extension of this method to other transformation rules such as endomorphise.
Affiliations:
- France
- Grand Est, Lorraine (région)
- Nancy
- Centre national de la recherche scientifique, Institut national de recherche en informatique et en automatique, Laboratoire lorrain de recherche en informatique et ses applications, Université de Lorraine
Links toward previous steps (curation, corpus...)
- to stream Crin, to step Corpus: 000267
- to stream Crin, to step Curation: 000267
- to stream Crin, to step Checkpoint: 004221
- to stream Main, to step Merge: 00F004
- to stream Main, to step Curation: 00E716
Le document en format XML
<record><TEI><teiHeader><fileDesc><titleStmt><title xml:lang="en" wicri:score="505">Proving termination of associative commutative rewriting systems by rewriting</title></titleStmt><publicationStmt><idno type="RBID">CRIN:gnaedig86a</idno><date when="1986" year="1986">1986</date><idno type="wicri:Area/Crin/Corpus">000267</idno><idno type="wicri:Area/Crin/Curation">000267</idno><idno type="wicri:explorRef" wicri:stream="Crin" wicri:step="Curation">000267</idno><idno type="wicri:Area/Crin/Checkpoint">004221</idno><idno type="wicri:explorRef" wicri:stream="Crin" wicri:step="Checkpoint">004221</idno><idno type="wicri:Area/Main/Merge">00F004</idno><idno type="wicri:Area/Main/Curation">00E716</idno><idno type="wicri:Area/Main/Exploration">00E716</idno></publicationStmt><sourceDesc><biblStruct><analytic><title xml:lang="en">Proving termination of associative commutative rewriting systems by rewriting</title><author><name sortKey="Gnaedig, I" sort="Gnaedig, I" uniqKey="Gnaedig I" first="I." last="Gnaedig">I. Gnaedig</name></author><author><name sortKey="Lescanne, P" sort="Lescanne, P" uniqKey="Lescanne P" first="P." last="Lescanne">Pierre Lescanne</name><affiliation><country>France</country><placeName><settlement type="city">Nancy</settlement><region type="region" nuts="2">Grand Est</region><region type="region" nuts="2">Lorraine (région)</region></placeName><orgName type="laboratoire" n="5">Laboratoire lorrain de recherche en informatique et ses applications</orgName><orgName type="university">Université de Lorraine</orgName><orgName type="institution">Centre national de la recherche scientifique</orgName><orgName type="institution">Institut national de recherche en informatique et en automatique</orgName></affiliation></author></analytic></biblStruct></sourceDesc></fileDesc><profileDesc><textClass><keywords scheme="KwdEn" xml:lang="en"><term>rewriting</term><term>termiation</term></keywords></textClass></profileDesc></teiHeader><front><div type="abstract" xml:lang="en" wicri:score="1943">We propose in this paper a special reduction ordering for proving termination of Associative Commutative (AC in short) rewriting systems. This ordering is based on a transformation of the terms by a rewriting system with rules similar to distributivity. We show this is a reduction ordering which works in the AC case since it is AC-commuting, and which provides an automatizable termination tool, since it is stable by instanciation. Thereafter, we show cases where this ordering fails, and propose an extension of this method to other transformation rules such as endomorphise.</div></front></TEI><affiliations><list><country><li>France</li></country><region><li>Grand Est</li><li>Lorraine (région)</li></region><settlement><li>Nancy</li></settlement><orgName><li>Centre national de la recherche scientifique</li><li>Institut national de recherche en informatique et en automatique</li><li>Laboratoire lorrain de recherche en informatique et ses applications</li><li>Université de Lorraine</li></orgName></list><tree><noCountry><name sortKey="Gnaedig, I" sort="Gnaedig, I" uniqKey="Gnaedig I" first="I." last="Gnaedig">I. Gnaedig</name></noCountry><country name="France"><region name="Grand Est"><name sortKey="Lescanne, P" sort="Lescanne, P" uniqKey="Lescanne P" first="P." last="Lescanne">Pierre Lescanne</name></region></country></tree></affiliations></record>Pour manipuler ce document sous Unix (Dilib)
EXPLOR_STEP=$WICRI_ROOT/Wicri/Lorraine/explor/InforLorV4/Data/Main/Exploration
HfdSelect -h $EXPLOR_STEP/biblio.hfd -nk 00E716 | SxmlIndent | more
Ou
HfdSelect -h $EXPLOR_AREA/Data/Main/Exploration/biblio.hfd -nk 00E716 | SxmlIndent | more
Pour mettre un lien sur cette page dans le réseau Wicri
{{Explor lien
|wiki= Wicri/Lorraine
|area= InforLorV4
|flux= Main
|étape= Exploration
|type= RBID
|clé= CRIN:gnaedig86a
|texte= Proving termination of associative commutative rewriting systems by rewriting
}}
| This area was generated with Dilib version V0.6.33. |  |